#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

#include "insertion-sort.h"
#include "counting.h"

using namespace std;

template <class T>
void printVet(T vet[], size_t size) {
	cout << "[";
	for(size_t i = 0; i < size; i++)
		cout << vet[i] << " ";
	cout << "]" << endl;
}

template<class T>
static size_t hash(int min, int max, size_t buckets, T value) {
	double result = ((double) (buckets))*((double) (value - min) )/( (double) (max - min));
	if((size_t) result == buckets)
		return buckets-1;
//	return (buckets-1)*((value - min)/(max - min));
	return (size_t) result;
}

typedef pair<size_t, size_t> range;

enum LocalSort {
	INS, COUNT, SORT
};

template <class T>
void bucketSort(T vet[], size_t size, size_t numBuckets, const range& numRange, LocalSort localSort) {

#ifdef DEBUG
	cout << "Vetor a ser ordenado: ";
	printVet<T>(vet, size);
#endif

	// Criando os buckets
	vector<vector<T> > buckets;
	for(size_t i = 0; i < numBuckets; i++)
		buckets.push_back(vector<T>());
	
	// Distribuindo numeros aos respectivos buckets
	for(size_t i = 0; i < size; i++) {
		size_t bucketIdx = hash(numRange.first, numRange.second, numBuckets, vet[i]);
		buckets.at(bucketIdx).push_back(vet[i]);
	}

#ifdef DEBUG
	cout << "Buckets (Antes da ordenacao):" << endl;
	for(size_t i = 0; i < numBuckets; i++) {
		cout << "  B" << i << " {";
		for(size_t j = 0; j < buckets.at(i).size(); j++)
			cout << buckets.at(i).at(j) << " ";
		cout << "}" << endl;
	}	
#endif

	if(localSort == SORT) {
		for(size_t i = 0; i < numBuckets; i++)
			sort(buckets.at(i).begin(), buckets.at(i).end());
	}
	else if(localSort == INS) {
		for(size_t i = 0; i < numBuckets; i++)
			insertion_sort(&(buckets.at(i).front()), buckets.at(i).size());
	}
	else if(localSort == COUNT){
		for(size_t i = 0; i < numBuckets; i++)
			counting_sort(&(buckets.at(i).front()), buckets.at(i).size(), numRange.first, numRange.second);
	}
	else  {
		cerr << "Metodo de ordenacao invalido! Abortando!" << endl;
		exit(2);
	}
	
#ifdef DEBUG
	cout << "Buckets (Depois da ordenacao):" << endl;
	for(size_t i = 0; i < numBuckets; i++) {
		cout << "  B" << i << " {";
		for(size_t j = 0; j < buckets.at(i).size(); j++)
			cout << buckets.at(i).at(j) << " ";
		cout << "}" << endl;
	}	
#endif
	
	// Concatenando os numeros dos buckets no buffer de saida
	size_t offset = 0;
	for(size_t i = 0; i < numBuckets; i++) {
		memcpy(vet + offset, &(buckets.at(i).front()), sizeof(T) * buckets.at(i).size());
		offset += buckets.at(i).size();
	}	
	
	
#ifdef DEBUG
	cout << "Vetor a ser ordenado: ";
	printVet<T>(vet, size);
#endif

}

int main(int argc, char* argv[])
{
	srand(time(NULL));
	if(argc != 6) {
		cerr << "Numero de parametros errado! Abortando!" << endl;
		exit(1);
	}
	
	int size = atoi(argv[1]);
	int numBuckets = atoi(argv[2]);
	long long min = atol(argv[3]);
	long long max = atol(argv[4]);
	
	// Gerando numeros aleatorios
	long long* vet = new long long[size];
	for(int i = 0; i < size; i++) {
		vet[i] = rand() % max + min;
	}
	
	if(strcmp(argv[5], "INS") == 0)
		bucketSort(vet, size, numBuckets, range(min, max), INS);
	else if(strcmp(argv[5], "COUNT") == 0)
		bucketSort(vet, size, numBuckets, range(min, max), COUNT);
	else if(strcmp(argv[5], "SORT") == 0)
		bucketSort(vet, size, numBuckets, range(min, max), SORT);
	else {
		cerr << "Metodo de ordenacao invalido! Abortando!" << endl;
		exit(2);
	}
	
	delete[] vet;
	
	return(0);
}
